\subsubsection{Solución elegida}

Como dijimos en la sección ``Ideas'', la solución que elegimos fue la golosa: Ordenar las máquinas por tiempo de producción decreciente asi podremos aprovechar el tiempo de proceso de la maquina que mas tarda para cargar otras maquinas y no estirar el tiempo total de produccion de todas las maquinas. La idea es usar la función \textit{sort} ya convenientemente pre-implementada en la biblioteca STL$(*)$ , aprovechando así su orden de complejidad ($O(n log(n))$) en el peor caso, como se puede observar lo unico que se hace en el algoritmo es ordenarlos de manera que podamos obtener la solucion optima al caso que estamos necesitando, con lo cual la complejidad se limita a la complejidad del Sort que hayamos elegido. La complejidad requerida para este algoritmo era $O(N^2)$ por lo que nuestro algoritmo ademas de devolver la solucion optima devuelve una complejidad mejor ya que $O(n log(n))$ \in $O(N^2)$.
\vspace{2cm}

\footerfancy{$Referencias:$ (*)http://www.cplusplus.com/reference/algorithm/sort/}
\subsubsection{Demostración}

Para demostrar que nuestro algoritmo resuelve el problema lo primero que necesitamos es una expresión que defina, dado un conjunto de $n$ máquinas y un orden $\{m_i\}_{1 \leq i \leq n}$, en qué momento $t$ (tomando como tiempo inicial el momento en el que comienza a ser cargada la primera máquina) la máquina $i$ termina de trabajar.

Como antes de que la máquina $i$ empiece a trabajar ésta debe ser cargada y todas las máquinas que se dispuso fueran cargadas antes también:

\begin{align*}
	t^{(m_i)} \geq \sum_{j=1}^{i} C^{(m_j)} &\text{	donde $C^{(m)}$ es el tiempo de carga de la máquina $m$} 
\end{align*}

Una vez que la máquina $i$ fue cargada, ésta comienza a trabajar hasta que termina, por lo que nos queda:

\begin{align*}
	t^{(m_i)} = \sum_{j=1}^{i} C^{(m_j)} + P^{(m_i)} &\text{	donde $P^{(m)}$ es el tiempo de trabajo de la máquina $m$} 
\end{align*}

Entonces, dado un orden de máquinas $\{m_i\}_{1 \le i \le n}$, el tiempo total que tarda el conjunto de máquinas en terminar es:

\begin{align*}
	T^{(\{m_i\}_{1 \le i \le n})} = max_{1 \le k \le n} ( \sum_{j=1}^{k} C^{(m_j)} + P^{(m_k)} )
\end{align*}

Ahora que definimos analíticamente cuál es el tiempo total que tarda un conjunto de máquinas en terminar de producir dado un determinado orden de carga, el siguiente paso es ver que si, estando las máquinas ordenadas decrecientemente por tiempo de trabajo, entonces el tiempo total de producción es mínimo u óptimo.

Dado un conjunto de máquinas, sean:
\begin{itemize}
	\item $\{m_i\}_{1 \le i \le n}$ la secuencia de máquinas ordenada de mayor a menor por tiempo de trabajo.
	\item $M \in \{m_i\}_{1 \le i \le n}$ tal que $t^{(M)} = T^{(\{m_i\}_{1 \le i \le n})}$, es decir $M$ es la máquina que más tardó en terminar.
	\item $M^{-} = \{m_i\}_{1 \le i \le \mu}$, donde $\mu$ es el índice de $M$ en $\{m_i\}_{1 \le i \le n}$. En otras palabras, $M^{-}$ contiene a $M$ y las máquinas que se deben cargar antes que $M$.
	\item $\{m_{O^{(i)}}\}_{1 \le i \le n}$ una secuencia que optimiza el tiempo total de producción. Llamémosla $opt$.
\end{itemize}
   
Como $M^{-} \subseteq \{m_{O^{(i)}}\}_{1 \le i \le n}$, puedo definir $M^{*} = m_{\sigma}$ con $\sigma = max_{1 \le i \le \mu}(O^{(i)})$. Así, $M^{*}$ es la última de las máquinas de $M^{-}$ que se carga en la secuencia $opt$.

Entonces:

\begin{align*}
	t_{opt}^{(M^{*})} = \sum_{j / O^{(j)} \le \sigma} C^{(m_{O^{(j)}})} + P^{(m_\sigma)}
\end{align*}

Además:

\begin{itemize}
	\item $\sum\limits_{j=1}^{\mu} C^{(m_j)} \le \sum\limits_{j / O^{(j)} \le \sigma} C^{(m_{O^{(j)}})}$, dado que $M^{-} \subseteq \{m_{O^{(i)}}\}_{i / O^{(i)} \le \sigma}$
	\item $P^{(m_{\mu})} \le P^{(m_{\sigma})}$, ya que $m_{\mu} \in M^{-}$, $m_{\sigma} \in M^{-}$ y $P^{(m_{\mu})} = min_{m \in M^{-}}(P^{(m)})$ por estar $M^{-}$ ordenado por tiempo de trabajo decreciente.
\end{itemize}

Entonces podemos plantear:

\begin{align*}
	T^{(\{m_i\}_{1 \le i \le n})} = t^{(M)} = \sum_{j=1}^{\mu} C^{(m_j)} + P^{(m_{\mu})} \le \sum_{j / O^{(j)} \le \sigma} C^{(m_{O^{(j)}})} + P^{(m_\sigma)} = t^{(M^{*})} \le T_{opt}^{(\{m_{O^{(i)}}\}_{1 \le i \le n})}
\end{align*}

De lo que se deduce que $T^{(\{m_i\}_{1 \le i \le n})} \le T_{opt}^{(\{m_{O^{(i)}}\}_{1 \le i \le n})}$. Por lo tanto, el tiempo de trabajo total del conjunto de máquinas es óptimo cuando se las ordena por tiempo de trabajo decreciente.

\subsubsection{Pseudocódigo}

Definimos el tipo $Maquina$ como $Tupla\langle Indice, Carga, Produccion\rangle$.

\begin{pseudocode}[ruled]{ObtenerTiempoOptimo}{Secuencia\langle Maquina\rangle \; maquinas}

	\LOCAL maquinasOrdenadas \GETS \CALL{Sort}{maquinas, \CALL{Comparar}} \\ \\
	\LOCAL tCargaAcumulado \GETS 0 \\
	\LOCAL tFinMaquinaActual \GETS 0 \\
	\LOCAL tFinGlobal \GETS 0 \\ \\
	\FOR i \GETS 0 \TO Tamanio(maquinasOrdenadas) - 1 \DO
	\BEGIN
		tCargaAcumulado \GETS tCargaAcumulado + maquinasOrdenadas[i].Carga \\
		tFinMaquinaActual \GETS tCargaAcumulado + maquinasOrdenadas[i].Produccion \\
		\IF tFinGlobal < tFinMaquinaActual \THEN
			tFinGlobal \GETS tFinMaquinaActual \\
		i \GETS i + 1 \\
	\END \\ \\
	
	\OUTPUT{maquinasOrdenadas, tFinGlobal}

\end{pseudocode}

\begin{pseudocode}[ruled]{Comparar}{Maquina \; maquina1, Maquina \; maquina2}

	\LOCAL result \GETS maquina1.Produccion > maquina2.Produccion \\ \\
	\RETURN {result}

\end{pseudocode}


